package DoublyLinkedList

import (
	"errors"
	"fmt"
	"strings"
	"sync"
)

// T 表示链表中元素的类型，使用泛型。
type T any

// ErrorOutOfRange 定义了一个超出范围的错误。
var ErrorOutOfRange = errors.New("out of range")

// node 表示链表中的一个节点，包含前后节点指针和数据值。
type node[T any] struct {
	prev  *node[T] // 指向前一个节点
	next  *node[T] // 指向下一个节点
	value T        // 节点的数据值
}

// list 定义了一个双向链表，包含头节点、尾节点、链表大小和互斥锁。
type list[T any] struct {
	head       *node[T]   // 链表的头节点
	tail       *node[T]   // 链表的尾节点
	sizeOflist uint64     // 链表的元素个数
	mutex      sync.Mutex // 锁，保证并发安全
}

// NewList 创建一个新的空链表。
func NewList[T any]() *list[T] {
	return &list[T]{
		head:       nil,
		tail:       nil,
		sizeOflist: 0,
		mutex:      sync.Mutex{},
	}
}

// Size 返回链表中元素的个数。
func (lst *list[T]) Size() uint64 {
	return lst.sizeOflist
}

// Empty 检查链表是否为空。
func (lst *list[T]) Empty() bool {
	return lst.sizeOflist == 0
}

// Clear 清空链表，将头尾指针置为 nil，大小置为 0。
func (lst *list[T]) Clear() {
	lst.mutex.Lock() // 锁定链表，确保线程安全
	defer lst.mutex.Unlock()
	lst.head = nil
	lst.tail = nil
	lst.sizeOflist = 0
}

// FrontNode 返回链表的头节点指针。
func (lst *list[T]) FrontNode() *node[T] {
	return lst.head
}

// BackNode 返回链表的尾节点指针。
func (lst *list[T]) BackNode() *node[T] {
	return lst.tail
}

// Next 返回当前节点的下一个节点。
func (ptr *node[T]) Next() *node[T] {
	if ptr == nil {
		return nil
	}
	return ptr.next
}

// Prev 返回当前节点的前一个节点。
func (ptr *node[T]) Prev() *node[T] {
	if ptr == nil {
		return nil
	}
	return ptr.prev
}

// SetValue 设置当前节点的值。
func (ptr *node[T]) SetValue(newValue T) {
	if ptr == nil {
		return
	}
	ptr.value = newValue
}

// GetValue 返回当前节点的值，如果节点为 nil 返回错误。
func (ptr *node[T]) GetValue() (T, error) {
	if ptr == nil {
		return *new(T), ErrorOutOfRange
	}
	return ptr.value, nil
}

// Front 返回链表头节点的值，如果链表为空，返回错误。
func (lst *list[T]) Front() (T, error) {
	if lst.Empty() {
		return *new(T), ErrorOutOfRange
	}
	return lst.head.value, nil
}

// Back 返回链表尾节点的值，如果链表为空，返回错误。
func (lst *list[T]) Back() (T, error) {
	if lst.Empty() {
		return *new(T), ErrorOutOfRange
	}
	return lst.tail.value, nil
}

// Insert 在指定节点 ptr 前或后插入新节点，并更新链表的头尾。
func (lst *list[T]) Insert(ptr *node[T], val T) {
	lst.mutex.Lock()
	defer lst.mutex.Unlock()
	// 创建新节点
	newNode := &node[T]{
		prev:  nil,
		next:  nil,
		value: val,
	}

	// 插入节点
	if ptr == nil { // 如果插入位置为 nil，则链表为空
		lst.head = newNode
		lst.tail = newNode
	} else {
		// 插入到 ptr 前或后
		pre := ptr.prev
		ptr.prev = newNode
		newNode.next = ptr
		newNode.prev = pre
		// 更新 ptr 前后的节点指针
		if pre != nil {
			pre.next = newNode
		} else {
			lst.head = newNode
		}
	}
	// 更新链表的大小
	lst.sizeOflist++
}

// PushFront 在链表的头部插入一个新节点。
func (lst *list[T]) PushFront(val T) {
	lst.mutex.Lock()
	defer lst.mutex.Unlock()
	// 创建新节点
	newNode := &node[T]{
		prev:  nil,
		value: val,
	}
	if lst.Empty() { // 链表为空时，头尾都指向新节点
		lst.head = newNode
		lst.tail = newNode
	} else {
		lst.head.prev = newNode // 将头节点的 prev 指向新节点
		newNode.next = lst.head // 将新节点的 next 指向头节点
		lst.head = newNode      // 将头指针指向新节点
	}
	lst.sizeOflist++ // 增加链表大小
}

// PushBack 在链表的尾部插入一个新节点。
func (lst *list[T]) PushBack(val T) {
	lst.mutex.Lock()
	defer lst.mutex.Unlock()
	// 创建新节点
	newNode := &node[T]{
		prev:  nil,
		value: val,
	}
	if lst.Empty() { // 链表为空时，头尾都指向新节点
		lst.head = newNode
		lst.tail = newNode
	} else {
		lst.tail.next = newNode // 将尾节点的 next 指向新节点
		newNode.prev = lst.tail // 将新节点的 prev 指向尾节点
		lst.tail = newNode      // 将尾指针指向新节点
	}
	lst.sizeOflist++ // 增加链表大小
}

// Remove 从链表中删除指定的节点。
func (lst *list[T]) Remove(ptr *node[T]) {
	lst.mutex.Lock()
	defer lst.mutex.Unlock()
	if ptr == nil { // 如果指针为空，抛出错误
		panic(ErrorOutOfRange)
	}
	if ptr == lst.head { // 如果是头节点
		lst.head = lst.head.next
		lst.head.prev = nil
	} else if ptr == lst.tail { // 如果是尾节点
		lst.tail = lst.tail.prev
		lst.tail.next = nil
	} else { // 中间节点
		ptr.prev.next = ptr.next
		ptr.next.prev = ptr.prev
	}
	ptr.prev = nil
	ptr.next = nil
	ptr.value = *new(T) // 释放节点的值
}

// PopFront 从链表的头部移除一个节点。
func (lst *list[T]) PopFront() {
	lst.mutex.Lock()
	defer lst.mutex.Unlock()
	if lst.Empty() { // 如果链表为空，抛出错误
		panic(ErrorOutOfRange)
	}
	if lst.sizeOflist == 1 { // 链表只有一个元素时，清空链表
		lst.Clear()
	} else { // 否则，删除头节点
		lst.Remove(lst.head)
		lst.sizeOflist--
	}
}

// PopBack 从链表的尾部移除一个节点。
func (lst *list[T]) PopBack() {
	lst.mutex.Lock()
	defer lst.mutex.Unlock()
	if lst.Empty() { // 如果链表为空，抛出错误
		panic(ErrorOutOfRange)
	}
	if lst.sizeOflist == 1 { // 链表只有一个元素时，清空链表
		lst.Clear()
	} else { // 否则，删除尾节点
		lst.Remove(lst.tail)
		lst.sizeOflist--
	}
}

// String 返回链表的字符串表示，从头到尾遍历链表。
func (lst *list[T]) String() string {
	var str strings.Builder
	str.WriteString("[")
	ok := false
	for pHead := lst.FrontNode(); pHead != nil; pHead = pHead.Next() { // 从头到尾遍历链表
		if ok {
			str.WriteString(" ")
		}
		str.WriteString(fmt.Sprintf("%v", pHead.value))
		ok = true
	}
	str.WriteString("]")
	return str.String()
}

// RString 返回链表的字符串表示，从尾到头遍历链表。
func (lst *list[T]) RString() string {
	var str strings.Builder
	str.WriteString("[")
	ok := false
	for pHead := lst.BackNode(); pHead != nil; pHead = pHead.Prev() { // 从尾到头遍历链表
		if ok {
			str.WriteString(" ")
		}
		str.WriteString(fmt.Sprintf("%v", pHead.value))
		ok = true
	}
	str.WriteString("]")
	return str.String()
}
